package com.oocl.sorter;

public class QuickSort {
	public static void sort(int[] arr){
		if(arr.length>0){
			quickSort(arr, 0, arr.length-1);
		}
	}
	
	/**
	 * 递归形式的分治排序
	 * @param arr
	 * @param min
	 * @param max
	 */
	public static void quickSort(int[] arr, int min, int max){
		if(min<max){
			int mid = getMiddle(arr, min, max);
			quickSort(arr, min, mid-1);
			quickSort(arr, mid+1, max);
		}
	}
	
	/**
	 * 查找中轴的位置,重点！
	 * @param arr 待查找的数组
	 * @param min	数组的起始位置
	 * @param max	数组结束的位置
	 * @return  中轴所在位置
	 */
	public static int getMiddle(int[] arr, int min, int max){
		int mid = arr[min];      //数组的第一个为中轴的值
		while(min<max){
			while(arr[max]>mid){
				max--;
			}
			arr[min] = arr[max];
			while(arr[min]<mid){
				min++;
			}
			arr[max] = arr[min];
		}
		arr[min] = mid;         ///吧中值还给arr[min]
		return min;
	}
}
